1. Field of the Invention
The present invention relates to a pattern model positioning method in image processing, an image processing apparatus, an image processing program, and a computer readable recording medium, for performing fine positioning with higher accuracy upon searching out of an image to be searched and positioning a pattern model corresponding to a pre-registered image.
2. Description of the Related Art
An image processing apparatus for processing an image picked up by an image pickup element typically includes: an image pickup apparatus for picking up an image processing object (hereinafter also referred to as “work”); an image data storing device for storing data on the image picked up by the image pickup apparatus; and an image data processing device for processing the image data stored by the image data storing device. For example, in the image processing apparatus where the image pickup apparatus is made up of a CCD camera, luminance data (so-called multi-valued data) such as 256 levels of gray or 1024 levels of gray is obtained based on each of charge amounts of a large number of charge coupled elements constituting an image pickup surface, whereby a position, a rotational angle and the like of the work as an object to be searched can be found. Conventionally, as techniques for performing processing on image data to search an object to be searched in image processing, there are known a difference search performed using a total value of absolute values of pixel difference values between images, a normalized correlation search performed using normalized correlation values between images, and the like. In these searches, an object to be searched that is wished to be searched is previously registered as a template image, and based on the image, a search is executed for the object to be searched out of an image to be searched. In these search processing, a region-based search by use of image data has conventionally been mainstream. However, such a conventional region-based search based on image thickness or the like has the problem of being susceptible to a change in illumination upon image pickup, and the like.
Meanwhile, there has also been provided a method for performing edge extraction processing on a registered image and an image to be searched, to perform a search based on edge information. In this method, a concentration value of pixels constituting image data is not used, but edge data based on an amount of change in concentration value is used, and hence it is possible to obtain the advantage of being not susceptible to fluctuations in illumination upon image pickup. Especially, in recent years, an edge-based pattern search with an edge regarded as a characteristic amount is drawing attention for its high robustness, and is in practical use in industrial applications and the like.
As a technique for improving a processing speed of a pattern search, a “coarse to fine” approach is known. Namely, first, a search is coarsely performed using a low-resolution image (coarse image), and after a rough position is specified, detailed positioning is performed using a high-resolution image (fine image), thereby to enhance accuracy of a position and posture. In the case of performing the edge-based search by means of coarse-to-fine type template matching, a pyramid search is used where a search is performed using coarse data obtained by compressing (also referred to as “thinning out” or the like) original data, to specify a rough position, and thereafter, a search is performed using detailed data. FIG. 87 shows a concept of the pyramid search. As shown in this drawing, a rough search (referred to as “coarse search” or the like) is performed using a low-resolution image having a high reduction ratio, to find a rough position. Thereafter, a search is performed in the vicinity thereof with an increased resolution and an intermediate reduction ratio, and finally, a fine search is performed on an image of an original size or an image having a reduction ratio close to the original size. As thus described, in the typical pyramid search, a plurality of images having changed resolutions are prepared, and a schematic position is first detected by use of an image having the lowest resolution. In subsequent processing, a search range is narrowed down to the vicinity of the previous detected position as the resolution is gradually increased. Thereby, the accuracy of the detected position enhances with each succeeding processing level, finally leading to detection of a highly accurate position with the resolution being that of the original image or closer thereto. As a technique concerning fine positioning for finding a position and posture with high accuracy by means of such coarse-to-fine type template matching, an image processing apparatus of Japanese Patent No. 3759983 is known.
This image processing apparatus includes: an image pickup apparatus for picking up an image processing object; an image data storing device for storing data on the image picked up by the image pickup apparatus; a search template data storing apparatus for storing data on a search template having a plurality of point pairs which are each made up of two points sandwiching an edge of the image processing object and also located at a fixed distance from each other that is larger than an array pitch of the image pickup devices of the image pickup apparatus, and are previously set correspondingly to a plurality of positions on the edge; and a determination device for determining the image processing object as an object to be searched that matches with the search template of the search template data storing device when the point pairs are taken as being in a matching state where one point of the pair is located inside the edge of the image processing object and the other is located within the background and the point pairs in an amount not smaller than a set amount out of the plurality of point pairs are in the matching state in a case where the search template is superimposed on a screen with image data of the image data storing device present therein and a difference state of an optical characteristic value of each point constituting the plurality of point pairs is larger than a set state. According to this apparatus, it is possible to see the presence or absence of the object to be searched and whether or not the image processing object is the object to be searched by use of the image data and the search template. Those can be determined by calculating and comparing optical characteristic values of two points constituting each of all point pairs, so that an image processing apparatus capable of readily and speedily performing processing can be obtained.
In this fine positioning, as described above, one-dimensional edge processing is performed on a seek-line to find an edge position, and a difference between an ideal point and the corresponding point is found. Using the difference and geometric information peculiar to a model (information such as a model being in rectangular shape, etc.) a displacement and a rotational angle are found. FIG. 88 shows the relation between a pattern detected upon registration and a seek-line SLN, and on the other hand, FIG. 89 shows a state immediately before fine positioning after a coarse search during motion. FIG. 90 shows an enlarged view of the lower left portion of FIG. 89. As a kernel of the edge, (−1, −1, −1 −1, 1, 1, 1, 1) shown in Table 1 below is employed. In edge detection, an edge is found by applying this kernel to a pixel value obtained by interpolation on the seek-line SLN.
TABLE 1−−−−++++
However, high accuracy cannot be expected in this technique because whether or not the corresponding point is present on the seek-line is determined based only upon the relation between a size of a differential value and its threshold and an edge direction and an angle component are not considered. Further, there has been a drawback with this technique in that processing cannot be performed in a case where a plurality of points as candidates of the corresponding point are present on the seek-line, e.g., a double line cannot be processed. Moreover, in this method, although positioning of a simple shape such as a rectangle and a circle can be realized, positioning of a general and multipurpose shape such as a more complicated shape and a character pattern cannot be performed. Furthermore, there has been a problem in that accurate edge detection cannot be performed on a thin-linear object to be searched due to the long kernel of the edge detection. Namely, a difference is computed along the line by the one-dimensional kernel in the longitudinal direction, to consider an edge. Especially, the kernel needs to be made longer in order to enhance noise resistance. There has consequently been a drawback in that, when a work itself is long and narrow, edge data becomes relatively weak, to be regarded as a noise component, and hence accurate edge detection cannot be expected.
Meanwhile, a fine positioning method by a least squares method using image points and segments is disclosed in I. J. Cox, J. B. Kruskal, and D. A. Wallach, “Predicting and Estimation the performance of a subpixel registration algorithm,” IEEE Trans. Pattern Anal. Machine Intell., vol. 12, no. 6, pp. 721-734, (August 1990). In this method, a pattern model is configured of segments. Further, error detection processing is performed on an image to be searched not yet inputted, to create an edge image including imaginary points. The pattern model is superimposed on a position in the edge image which was decided by a coarse search, and a least squares method is performed using as an error value a distance between a point and a straight line, which are every image point in the image to be searched and a segment inside the pattern model that is close to the image point, to decide a fine position. In an example of FIG. 91 shown is the relation between a pattern model configured of two segments and image points (input image points) in an image to be searched.
However, there has been a problem with this technique in that, since the corresponding relation between the segment and the point depends only upon the distance therebetween, a point may be computed as the corresponding point even in an inherently non-corresponding relation with the segment in view of the edge direction or the like. Further, there has also been a problem in that, from necessity of acquiring imaginary points in the image to be searched, the edge detection needs to be performed on every point in a high resolution image as an object to be searched, and hence round-robin processing is performed, leading to an increase in processing time with increase in resolution of the image data.